package com.zyk.grate_offer.class01;

/**
 * 一个数组中只有两种字符'G'和'B’，
 * 想让所有的G都放在左侧，所有的B都放在右侧
 * 或所有的B都放在左侧，所有的G都放在右侧
 * 但是只能在相邻字符之间进行交换操作，
 * 返回至少需要交换几次
 *
 * @author zhangsan
 * @date 2021/4/21 10:07
 */
public class Code04_MinSwapStep {

    // 贪心, 计算将所有 G都放在左边 或 B都放在左边需要的最少交换次数
    // 不需要每种都尝试
    public static int minStep1(String s) {
        int N = s.length();
        int gi = 0, bi = 0;
        int stepG = 0, stepB = 0;
        for (int i = 0; i < N; i++) {
            if (s.charAt(i) == 'G') {
                stepG += (i - gi++);
            } else {
                stepB += (i - bi++);
            }
        }
        return Math.min(stepB, stepG);
    }

    // for test
    public static void main(String[] args) {
        String str = "GGBBGGBG";
        System.out.println(minStep1(str));
    }

}
